#include "thread.h"
#include <stdio.h>
#include <assert.h>
//#include <pthread.h>
#include <stdlib.h>

struct tableau {
  int* t;
  int deb;
  int fin;
};

void* tri_fusion (void* arg) {
  
  struct tableau *tab = (struct tableau*)arg;
  
  if(tab->deb < tab->fin) {
    int k =(int) (tab->deb + tab->fin)/2;
    pthread_t t1, t2;
    
    struct tableau *tab1, *tab2;
    tab1 = malloc(sizeof(*tab1));
    tab2 = malloc(sizeof(*tab2));
    
    tab1->t = tab->t;
    tab1->deb = tab->deb;
    tab1->fin = k;
    tab2->t = tab->t;
    tab2->deb = k+1;
    tab2->fin = tab->fin;
    
    pthread_create(&t1, NULL, tri_fusion, (void*)tab1);
    pthread_create(&t2, NULL, tri_fusion, (void*)tab2);
    
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    
    int * tmp1 = malloc(sizeof(int)*(k - tab->deb + 1));
    int * tmp2 = malloc(sizeof(int)*(tab->fin - k));
    
    int i1, i2;
    for(i1 = 0; i1 <= (k - tab->deb); i1++) {
      //printf("i1: %d | k-deb: %d\n", i1, k-tab->deb);
      tmp1[i1] = tab->t[tab->deb+i1];
    }
    for(i2=0; i2 < (tab->fin - k); i2++) {
      //printf("i2: %d | fin-k: %d\n", i2, tab->fin - k);
      tmp2[i2] = tab->t[i2+k+1];
  }
    
    i1=0;i2=0;
    while((i1 <= (k - tab->deb)) && (i2 < (tab->fin - k))) {
      if(tmp2[i2] < tmp1[i1]) {
	//printf("A deb+i1+i2: %d | i1: %d | i2: %d\n", tab->deb+i1+i2, i1, i2);
	tab->t[tab->deb+i1+i2] = tmp2[i2];
	i2 ++;
      }
      else {
	//printf("B deb+i1+i2: %d | i1: %d | i2: %d\n", tab->deb+i1+i2, i1, i2);
	tab->t[tab->deb+i1+i2] = tmp1[i1];
	i1++;
      }
    }
    
    while(i1 <= (k - tab->deb)){
      //printf("C deb+i1+i2: %d | i1: %d | i2: %d\n", tab->deb+i1+i2, i1, i2);
      tab->t[tab->deb+i1+i2] = tmp1[i1];
      i1++;
    }
    
    while(i2 < (tab->fin - k)){
      //printf("D deb+i1+i2: %d | i1: %d | i2: %d\n", tab->deb+i1+i2, i1, i2);
      tab->t[tab->deb+i1+i2] = tmp2[i2];
      i2 ++;
    }
    


    free(tab1);
    free(tab2);
  }
    
    return NULL;
}



void rand_tab(int *t, int taille) {

  int w;
  for(w = 0; w < taille; w++) {
    t[w] = (int)(rand()/1000000);
    if(t[w] < 0)
      t[w] = -t[w];
  }

}



int main () {

  int taille = 200;
  int A[taille];

  rand_tab(A, taille);

  struct tableau t;
  int i;
  t.t = A;
  t.deb = 0;
  t.fin = taille - 1;

  for(i = 0; i < taille; i++)
  printf("%d * ", A[i]);

  printf("\n");
  tri_fusion((void*) &t);


  for(i = 0; i < taille; i++)
    printf("%d * ", A[i]);

  printf("\n");

  return 38;
}
